package bin_tree.oj;

public class JZ36 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null || (pRootOfTree.left == null &&
                pRootOfTree.right == null)){
            return pRootOfTree;
        }
        TreeNode left = Convert(pRootOfTree.left);
        TreeNode leftTail = left;
        while (leftTail != null && leftTail.right != null){
            leftTail = leftTail.right;
        }
        if (pRootOfTree.left != null){
            leftTail.right = pRootOfTree;
            pRootOfTree.left = leftTail;
        }
        TreeNode right = Convert(pRootOfTree.right);
        if (pRootOfTree.right != null){
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }

        return pRootOfTree.left == null ? pRootOfTree : left;
    }
}
